Word Search
Medium
Question
Given an m*n grid of characters and a target string, return whether the target string exists on the board.
The word can be constructed sequentially via adjacent cells. For example, you can create the word by going veritcally, horizontally or a combination of both.
Input: board = [["A", "S", "B", "X", "E"], ["K", "O", "O", "O", "U"], ["F", "E", "S", "O", "O"], ["B", "A", "L", "M", "B"]], word = "BOOM"
Output: True
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: True
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Do you need a visited set? If yes, what is the strategy for adding / subtracting to this data structure?
No, we do not need a visited set.
Yes, the strategy is to add to the visited set whenever we visit the square.
Yes, the strategy is to add to the visited set whenever we are using the character as part of the word.
All test cases pass! 🎉
Time limit exceeded
InputExpected OutputActual Output
Standard OutputScroll down...
Login or signup to save your code.
Uh oh... looks like you don't yet have access.
Not sure what this unlocks? Check out a free pattern section.
Example solution
Complexity
